package com.jeff.meta.builder;

import com.jeff.meta.model.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * {@Description} 二叉树工具类
 * {@Author} <b style="color:yellow">yaojianfeng</b> 2024/7/7 下午10:40
 */
public class BinaryTreeUtil {

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        TreeNode<Integer> root = buildTreeByQueue(arr);
        TreeNode<Integer> integerTreeNode = buildTreeByRecursion(arr,0);
        System.out.println(root);
        System.out.println(integerTreeNode);
    }

    /**
     * 根据给定的数组元素,构建完全二叉树
     * 使用队列实现
     * @param arr 给定的数组
     * @return 根节点
     */
    public static TreeNode<Integer> buildTreeByQueue(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }

        TreeNode<Integer> root = new TreeNode<>(arr[0]);
        Queue<TreeNode<Integer>> queue = new LinkedList<>();
        queue.add(root);

        int i = 1;
        while (!queue.isEmpty() && i < arr.length) {
            TreeNode<Integer> currentNode = queue.poll();
            if (i < arr.length) {
                currentNode.left = new TreeNode<>(arr[i++]);
                queue.add(currentNode.left);
            }
            if (i < arr.length) {
                currentNode.right = new TreeNode<>(arr[i++]);
                queue.add(currentNode.right);
            }
        }

        return root;
    }

    /**
     * 根据给定的数组元素,构建完全二叉树
     * 使用递归实现
     * @param arr 给定的数组
     * @param index 当前节点的索引
     * @return 根节点
     */
    public static TreeNode<Integer> buildTreeByRecursion(int[] arr, int index) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        if (index >= arr.length) {
            return null;
        }
        TreeNode<Integer> root = new TreeNode<>(arr[index]);
        root.left = buildTreeByRecursion(arr, 2 * index + 1);
        root.right = buildTreeByRecursion(arr, 2 * index + 2);
        return root;
    }
}
